1. Field of the Invention
The present invention relates to a method and apparatus for improving the efficiency of process scheduling in a multiprocess system.
2. Art Background
In a time sharing computer system the CPU is allocated to a process for a pre-determined period of time called a time-slice or time quantum at the end of which the process is pre-empted and a second process is scheduled to begin at the start of the first new time-slice. The process preempted is then rescheduled to continue execution at a later time-slice. Process scheduling techniques are employed to determine the order in which processes have access to the CPU.
Process scheduling techniques have been extended to multiple-CPU computer systems. Processes are allocated a time-slice according to the CPU available. A process table is maintained which identifies each process to be executed. Each process table entry identifying a process contains a priority field for a process scheduling. For example, the priority of a process may be a function of the amount of its CPU usage with processes getting a lower priority if they have recently used the CPU. A process scheduler accesses the process table information and controls which processes are allocated the usage of the CPU. For information on process scheduling see The Design of the UNIX.RTM. Operating System, Maurice J. Bach, pages 247-258 (Prentice-Hall, Inc., 1986) and Operating System Concepts, 3rd Ed., Silber Schetz, Peterson and Galvin, pages 97-125 (Addison-Wesley, 1991).
Typically in a multiple CPU system, the scheduler will allocate the next available CPU to the process having the highest priority for scheduling. However, as the multiple process systems become more sophisticated, other factors must be considered in scheduling processes to achieve the best results. In particular, in a multiple CPU system, cache memories are now allocated to each CPU. Applying currently known scheduling techniques results in poor usage and efficiency of the cache memories. This is illustrated with respect to FIG. 1. FIG. 1a shows at time T0, there are five processes in the process queue indicating those processes are ready to be executed: A, B, C, D, and E. Since no processes have been executed at time T0, the cache contents and the process context for each processor are empty.
Referring to FIG. 1b at time T1, the first process is allocated to the first processor, Processor 1. Thus, the process context currently executing on Processor 1 is Process A and contents of the cache contain data related to Process A. At time T2, referring to FIG. 1c, the next process of highest priority is allocated to execute on Processor 2. Therefore, the process context of Processor 2 is Process B and the contents of the cache contain data related to Process B. At time T3, as shown in FIG. 1d, a context switch is performed wherein Process A is swapped out from the CPU and the process of highest priority, Process C, is swapped in to be executed by Processor 1. Thus, the context of Processor 1 is Process C. After some execution of Process C, the cache contents will contain data related to Process C as well as pre-existing data located in the cache related to Process A. At time T4, referring to FIG. 1e, a context switch is performed on Processor 2, wherein Process B is swapped out and Process D, the next process to be executed, is swapped in. Thus, Processor 2 is executing Process D and the cache contents of the cache memory associated with Processor 2 contains a mixture of data related to Process B and Process D. Continuing the pattern, it is evident that Process E will be scheduled on Processor 1 and Processor 2 will pick Process A from the run queue to execute next. This exposes a critical flaw in extending current scheduling algorithms to multiple CPU systems. In particular, current scheduling algorithms do not account for performance penalty of process shuffling among multiple processors. This penalty results from a "cold start" of the cache on the new processor which could avoided by scheduling the process on a CPU whose cache already contains data associated with the process. A method of scheduling which weighs this penalty in the scheduling algorithm would greatly improve the performance. For purposes of the following discussion, a cache is said to be cold relative to a particular process when it contains little or no data required for the execution of that process and accesses to the cache will miss. A cache is said to be warm with respect to a particular process when it contains data required for the execution of the process and accesses to the cache will hit.
Referring to FIG. 1f, the pattern of processor allocation can be extended to the processors so that over time a history of processors each process executes on can be determined. Note that Process A, which previously ran on Processor 0 will be restarted on Processor 1 and will not execute on Processor 0 until two processes (C and E) have previously executed on Processor 0. This ensures that much of the data from Process A in Processor 0's cache will have been replaced with data from Processes C and E. If the scheduling interval is approximately equal to the time it takes for the executing process to fill half of the cache, it can be seen that each process executes at best from a half-full cache when one or more intervening process have run on the CPU. Rescheduling takes place at every other time interval, such that the rescheduling executions are out of phase with one another.